﻿namespace ConsoleApp1
{

    class Program
    {
        static void Main(string[] args)
        {
            List<string> solutions = FindExpressions(new int[] { 9, 8, 7, 6, 5, 4, 3, 2, 1 }, 100);

            foreach (string expr in solutions)
            {
                Console.WriteLine(expr+"=100");
            }
        }

        static List<string> FindExpressions(int[] nums, int target)
        {
            List<string> result = new List<string>();

            // 回溯函数
            void Backtrack(string expression, int pos, long currentValue, long lastValue)
            {
                if (pos == nums.Length) // 如果遍历完成所有数字
                {
                    if (currentValue == target) // 检查结果是否等于目标值
                    {
                        result.Add(expression);
                    }
                    return;
                }

                int currentNum = nums[pos];

                // 加号操作
                Backtrack(expression + "+" + currentNum, pos + 1, currentValue + currentNum, currentNum);

                // 减号操作
                Backtrack(expression + "-" + currentNum, pos + 1, currentValue - currentNum, -currentNum);

                // 拼接操作 (不加操作)
                if (pos > 0) // 确保不拼接第一个数字
                {
                    long newLastValue = lastValue * 10 + currentNum;
                    if (lastValue < 0) newLastValue = lastValue * 10 - currentNum;
                    long newCurrentValue = currentValue - lastValue + newLastValue;
                    Backtrack(expression + currentNum, pos + 1, newCurrentValue, newLastValue);
                }
            }

            // 从第一个数字开始，初始化第一个数字
            Backtrack(nums[0].ToString(), 1, nums[0], nums[0]);

            return result;
        }
    }

}
